package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class climbStairs_ {
  public static void main(String[] args) {
    System.out.println(climbStairs(3));
  }

  // 1. dp[i]表示i级楼梯有dp[i]种方法到达楼顶
  // 2. 递推公式: dp[i] = dp[i - 1]  + dp[i + 2];
  // 3. dp数组初始化dp[0] = 0;dp[1] = 1;
  // 4. 遍历顺序: 从前向后遍历
  public static int climbStairs(int n) {
    if (n == 1){
      return 1;
    }
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2 ; i <= n ; i++){
        dp[i] = dp[i - 1]  +  dp[i - 2];
    }
    return dp[n];
  }
}
